Search for: All records

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is a branching program where each node is allowed to make 𝔽₂-linear queries, and is read-once in the sense that the queries on each path is linearly independent. As their main result, they constructed an explicit function with average-case complexity 2^{n/3-o(n)} against a slightly restricted model, which they call strongly read-once linear branching programs. The main tool in their lower bound result is a new type of extractor, called directional affine extractors, that they introduced. Our main result is an explicit function with 2^{n-o(n)} average-case complexity against the strongly read-once linear branching program model, which is almost optimal. This result is based on a new connection from this problem to sumset extractors, which is a randomness extractor model introduced by Chattopadhyay and Li (STOC '16) as a generalization of many other well-studied models including two-source extractors, affine extractors and small-space extractors. With this new connection, our lower bound naturally follows from a recent construction of sumset extractors by Chattopadhyay and Liao (STOC '22). In addition, we show that directional affine extractors imply sumset extractors in a restricted setting. We observe that such restricted sumset sources are enough to derive lower bounds, and obtain an arguably more modular proof of the lower bound by Gryaznov, Pudlák and Talebanfard. We also initiate a study of pseudorandomness against linear branching programs. Our main result here is a hitting set generator construction against regular linear branching programs with constant width. We derive this result based on a connection to Kakeya sets over finite fields. 

The area of randomness extraction has seen interesting advances in recent years, with rapid progress on many longstanding open problems, along with the introduction of many new notions that played a key role in this development. We survey this progress and highlight new definitions and notions that have been the subject of intense study in recent work. 

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem. 

We explicitly construct an extractor for two independent sources on 𝑛 bits, each with min-entropy at least log𝐶𝑛 for a large enough constant 𝐶. Our extractor outputs one bit and has error 𝑛−Ω(1). The best previous extractor, by Bourgain, required each source to have min-entropy .499𝑛. A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean function on 𝑛 bits that is resilient to coalitions of size 𝑛1−𝛿 for any 𝛿>0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on 𝑛 bits, where some unknown 𝑛−𝑞 bits are chosen almost polylog(𝑛)-wise independently, and the remaining 𝑞=𝑛1−𝛿 bits are chosen by an adversary as an arbitrary function of the 𝑛−𝑞 bits. The best previous construction, by Viola, achieved 𝑞=𝑛1/2–𝛿. Our explicit two-source extractor directly implies an explicit construction of a 2(loglog𝑁)𝑂(1)-Ramsey graph over 𝑁 vertices, improving bounds obtained by Barak et al. and matching an independent work by Cohen.